/***************************************************************************************
* Copyright (c) 2014-2022 Zihao Yu, Nanjing University
*
* NEMU is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*          http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
*
* See the Mulan PSL v2 for more details.
***************************************************************************************/

#include <isa.h>
#include <memory/vaddr.h>
/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>

enum {
  TK_NOTYPE = 256, TK_EQ, TK_NEQ, TK_LOGIC_AND, TK_NEG, TK_DEREF,

  /* TODO: Add more token types */
  TK_DECIMAL, TK_HEXADEC, TK_REG
};

static int priority[270];

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},    // spaces
  {"\\+", '+'},         // plus
  {"-", '-'},           // minus(双目运算符) 或负号(单目运算符)
  {"\\*", '*'},         // multiply(双目运算符) 或指针(单目运算符)
  {"/", '/'},           // divide
  {"==", TK_EQ},        // equal
  {"!=", TK_NEQ},        // not equal
  {"&&", TK_LOGIC_AND},        // 逻辑与
  {"\\(", '('},           // (
  {"\\)", ')'},           // )
  {"\\$[a-zA-Z0-9]+", TK_REG},   // register
  {"0x[0-9]+", TK_HEXADEC},   // hexadecimal
  {"[0-9]+u?", TK_DECIMAL},   // decimal
};

#define NR_REGEX ARRLEN(rules)
#define MAX_TOKEN 4096

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
  // 初始化优先级
  priority[TK_NOTYPE] = priority[TK_DECIMAL] = priority[TK_HEXADEC] = priority[TK_REG] = priority['('] = priority[')'] = 100;
  priority[TK_NEG] = priority[TK_DEREF] = 20;
  priority['*'] = priority['/'] = 10;
  priority['+'] = priority['-'] = 5;
  priority[TK_EQ] = priority[TK_NEQ] = 0;
  priority[TK_LOGIC_AND] = 0;
}

typedef struct token {
  int type;
  char str[32];
} Token;

static Token tokens[MAX_TOKEN] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */

        switch (rules[i].token_type) {
            case TK_NOTYPE: break;
            default:
                tokens[nr_token].type = rules[i].token_type;
                strncpy(tokens[nr_token].str, substr_start, substr_len);
                tokens[nr_token].str[substr_len] = '\0';// 设置字符串终点，防止后续非0值影响。
                nr_token++;
        }

        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

// BNF expression
uint32_t eval(int p, int q, bool *success);
bool check_parentheses(int p, int q, bool *success);
int searchMainOp(int p, int q);

uint32_t eval(int p, int q, bool *success){
    // 处理表达式及运算符
    if(p > q) {
        *success = false;
        printf("子表达式%d-%d不存在\n", p, q);
        return 0;
    } else if (p == q){
        // <decimal-number> | <hexadecimal-number> | <reg_name>
        // The token should be decimal, hexadecimal (0x) or regiester ($)
        uint32_t res;
        if(tokens[p].str[0]=='$') res = isa_reg_str2val(tokens[p].str + 1, success);
        else if(tokens[p].str[0]=='0' && tokens[p].str[1]=='x') sscanf(tokens[p].str, "0x%x", &res);
        else sscanf(tokens[p].str, "%u", &res);
        return res;
    } else if (check_parentheses(p, q, success) == true) {
        return eval(p+1, q-1, success);
    } else {
        // 处理表达式中的运算符
        // 非法表达式
        if(!*success) {
            assert(0);
            return 0;
        }
        // 正确表达式，寻找主运算符，单目运算符-和*一定要保证和后面参数结合
        int op = searchMainOp(p, q);
        uint32_t val2 = eval(op+1, q, success);
        if (tokens[op].type==TK_DEREF) {
            return vaddr_read(val2, 4);
        } else if (tokens[op].type==TK_NEG) {
            return -val2;
        }
        uint32_t val1 = eval(p, op-1, success);
        switch(tokens[op].type) {
            case '+': return val1 + val2;
            case '-': return val1 - val2;
            case '*': return val1 * val2;
            case '/': return val1 / val2;
            case TK_EQ: return val1 == val2;
            case TK_NEQ: return val1 != val2;
            case TK_LOGIC_AND: return val1 && val2;
            default: assert(0);
        }
    }

}

bool check_parentheses(int p, int q, bool *success){
    // TODO: 考虑存储()的匹配结果，可以节约每次都要扫描的问题
    if ((tokens[p].type!='(') | (tokens[q].type!=')')) {
        // 左右两侧不为()，没有必要检测匹配
        return false;
    } else {
        // 左右两侧为()
        bool is_parenthese = true;
        int left_n = 0, right_n = 0;
        for(int i=p+1; i<=q-1; i++) {//两侧不需要统计，统计内侧是否先出现右括号)right_n
            switch(tokens[i].type){
                case '(': left_n++; break;
                case ')': right_n++; break;
            }
            if (left_n < right_n) {
                // 最外侧括号不是一对
                is_parenthese = false;
            }
        }
        if (left_n != right_n){
            // 非法表达式
            *success = false;
            assert(0);
            return false;
        } else if (is_parenthese) return true;
        else return false;
    }
}

bool parentheses(int p, int q){
    int left_n = 0, right_n = 0;
    for(int i=p; i<=q; i++) {
        switch(tokens[i].type){
            case '(': left_n++; break;
            case ')': right_n++; break;
        }
    }
    if (left_n != right_n){
        // 非法表达式
        return false;
    }
    return true;
}

int searchMainOp(int p, int q) {
    int parentheses_n = 0, op = p, type = TK_NOTYPE;//初始化type为最高优先级
    for(int i=p; i<=q; i++) {
        if (tokens[i].type=='(') {
            parentheses_n += 1;
        } else if (parentheses_n>0) {
            if(tokens[i].type==')') parentheses_n -= 1;
        } else {
            // 不处于括号内部
            // 如果+-直接选择，*/只有在*/时更新
            // 这里相当于把运算符优先级hard-code了，优先级顺序 LOGIC OPERATOR, EQ NEQ, +-,  */, DEREF NEG, 
            if (priority[tokens[i].type] <= priority[type]){
                type = tokens[i].type;
                op = i;
            }
        }
    }
    return op;
}

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }

  /* TODO: Insert codes to evaluate the expression. */
  // 根据教程框架，遍历更新单目运算符类型
  // 单目运算符出现在表达式最左端，或者运算符左侧是运算符
  // 我在类型里特地将运算符放在一起TK_EQ到TK_DEREF之间
  for (int i=0; i < nr_token; i++) {
      if (tokens[i].type=='*' && 
              (i==0 || tokens[i-1].type=='(' || tokens[i-1].type=='+' || tokens[i-1].type=='-' || tokens[i-1].type=='*' || tokens[i-1].type=='/' || (tokens[i-1].type>=TK_EQ && tokens[i-1].type<=TK_DEREF)))
          tokens[i].type=TK_DEREF;
      if (tokens[i].type=='-' && (i==0 || tokens[i-1].type=='(' || tokens[i-1].type=='+' || tokens[i-1].type=='-' || tokens[i-1].type=='*' || tokens[i-1].type=='/' || (tokens[i-1].type>=TK_EQ && tokens[i-1].type<=TK_DEREF)))
          tokens[i].type=TK_NEG;
  }
  // 计算表达式
  // 检查括号匹配
  *success = parentheses(0, nr_token); // initialize success
  if(!*success) { printf("括号不匹配\n"); return 0;}
  word_t res = eval(0, nr_token-1, success);

  return res;
}
